package com.Offer;

/*
    面试题11：旋转数组的最小数字
    题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的 旋转。
    输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
    例如 数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为 1。
    特殊：{1,0,1,1,1}和{1,1,1,0,1}都是{0,1,1,1,1}的旋转数组，但是index1和index2和indexMid都相等，只能用顺序查找
 */
public class demo11 {

    public static void main(String[] args) throws Exception {
        int[] input = new int[]{1,0,1,1,1};
        System.out.println(Min(input,input.length));
    }

    public static int Min(int[] data,int length) throws Exception {

        if(data == null || length<0){
            throw new Exception("Invalid parameters");
        }
        int index1 = 0;
        int index2 = length-1;
        int indexMid = index1;

        while(data[index1] >= data[index2]){

            if(index2-index1 == 1){
                indexMid = index2;
                break;
            }
            indexMid = (index1+index2)/2;
            //如果遇到index1、index2、indexMid都相等的情况，就无法判断indexMid属于第一个数组还是第二个数组，只能顺序查找
            if(data[index1] == data[index2] && data[index1] == data[indexMid]){
                return MinInOrder(data,index1,index2);
            }

            if(data[indexMid] >= data[index1]){
                index1 = indexMid;
            }else if(data[indexMid] <= data[index2]){
                index2 = indexMid;
            }
        }
        return data[indexMid];
    }

    public static int MinInOrder(int[]data,int index1,int index2){
        int res = data[index1];
        for(int i = index1+1;i<=index2;++i){
            if(res > data[i]){
                res = data[i];
            }
        }
        return res;
    }

}
